package 判断子序列;

/**
 * @author: AirMan
 * @date: 2025/5/18 13:50
 * @description:
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
 * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。
 * 在这种情况下，你会怎样改变代码？
 */
public class Solution2 {
    public boolean isSubsequence(String s, String t) {
        // 确定dp数组（dp table）以及下标的含义:dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
        // 确定递推公式: if (s[i - 1] == t[j - 1])  t中找到了一个字符在s中也出现了 if (s[i - 1] != t[j - 1])
        //          相当于t要删除元素，继续匹配  if (s[i - 1] == t[j - 1])，
        //          那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，
        //          相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
        //          if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，
        //          那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
        int subLen = s.length();
        int mainLen = t.length();

        int[] dp = new int[subLen + 1];

        for (int i = 0; i < mainLen; i++) {
            // 需要使用上一轮的dp[j - 1]，所以使用倒序遍历
            for (int j = subLen; j > 0; j--) {
                // i遍历的是t字符串，j遍历的是dp数组，dp数组的长度比s的大1，因此需要减1。
                if (t.charAt(i) == s.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                }
            }
        }

        return dp[subLen] == subLen;
    }
}
